Home

Informatik 6

Ordnung schaffen - Listen

Eines der Hauptprobleme in unserer Zeit ist die Verwaltung großer Datenmengen. Die Auswertung dieser Daten setzt voraus, dass man diese in einer bestimmten Weise ordnet, so dass man anschließend gewünschte Daten schnell findet. Dazu stellt die Informatik verschiedene Datenstrukturen zur Verfügung. Die ersten dieser Strukturen sind sogenannte Listen.

Die (verkettete) Liste ist eine dynamische Datenstruktur, die eine Speicherung von miteinander in Beziehung stehenden Objekten erlaubt. Die Anzahl der Objekte ist im Vorhinein nicht bestimmt. Die Liste wird durch Zeiger auf die jeweils folgende(n) Knoten oder Speicherzellen des Arbeitsspeichers realisiert.

Auf diese Weise kann ein Programm die einzelnen Listenelemente "durchwandern" um die Liste zu sortieren oder um ein bestimmtes Element in einer sortierten Liste zu finden. Sortieren und Suchen sind die zwei Hauptaufgaben derartiger Programme. Wir wollen uns nun ansehen, wie man an eine solche Aufgabe herangeht.

Sortieralgorithmen

Ein Algorithmus ist eine eindeutige Handlungsvorschrift zur Lösung eines Problems oder einer Klasse von Problemen. Algorithmen bestehen aus endlich vielen, wohldefinierten Einzelschritten. Somit können sie zur Ausführung in ein Computerprogramm umgesetzt werden, aber auch in menschlicher Sprache formuliert werden. Bei der Problemlösung wird eine bestimmte Eingabe in eine bestimmte Ausgabe überführt.
Es gibt eine große Anzahl von zum Teil sehr komplizierten Algorithmen zum Sortieren von Daten. Wir wollen uns einige einfache ansehen und sie nachvollziehen.

Das Bubblesort-Verfahren

Die Regeln für dieses Verfahren lauten folgendermaßen:
  1. Durchlaufe die Liste von links nach rechts. Vergleiche in jedem Schritt das aktuelle Element mit dem rechten Nachbarn. Ist der rechte Nachbar kleiner, dann tausche die Elemente
  2. Am Ende des Durchgangs steht nun das größte Element am Ende der Liste und muss beim nächsten Durchlauf nicht mehr beachtet werden.
  3. Das Verfahren wird solange wiederholt, bis die Eingabeliste vollständig sortiert ist.


Man sieht auf den ersten Blick, dass dieses Verfahren nicht besonders effektiv ist. Deshalb hier ein deutlich besseres Verfahren:

Das Selectionsort-Verfahren

Die Regeln für dieses Verfahren lauten folgendermaßen:
  1. Beginne mit dem ersten Element in der Liste und suche nach dem kleinsten Element in der restlichen Liste. Vertausche nun das gefundene Element mit dem ersten Element. (Ausnahme: Das erste Element ist das kleinste Element. Dann bleibt es natürlich stehen.). Dieses erste Element ist nun der sortierte Teil der Liste.
  2. Fahre nun mit dem zweiten Element fort und gehe genauso wie oben vor, d.h. suche nach dem kleinsten Element im unsortierten Teil der Liste.
  3. Gehe nun in der restlichen Liste genauso vor bis die gesamte Liste sortiert ist.


Andere Verfahren arbeiten noch wesentlich effektiver, sind aber auch deutlich komplizierter und auf große Datenmengen ausgerichtet.

Suchalgorithmen

Nachdem die Daten geordnet sind, kann man sie nutzen um bei Bedarf bestimmte Daten zu suchen. Auch hier gibt es viele geeignete Algorithmen.

Lineare Suche

Das einfachste und zugleich am wenigsten effektive Verfahren ist eine lineare Suche. Dabei beginnt man beim ersten Element der Liste und geht solange weiter, bis man das gesuchte Element gefunden hat. Im schlechtesten Fall benötigt man genauso viele Überprüfungen wie die Liste Elemente besitzt. Viel effektiver ist zum Beispiel eine binäre Suche:

Binäre Suche

Die binäre Suche funktioniert folgendermaßen:

Zuerst wird das mittlere Element des Felds überprüft. Es kann kleiner, größer oder gleich dem gesuchten Element sein. Ist es kleiner als das gesuchte Element, muss das gesuchte Element in der hinteren Hälfte stecken, falls es sich dort überhaupt befindet. Ist es hingegen größer, muss nur in der vorderen Hälfte weitergesucht werden. Die jeweils andere Hälfte muss nicht mehr betrachtet werden. Ist es gleich dem gesuchten Element, ist die Suche beendet.
In der zu untersuchenden Hälfte (und erneut in den folgenden Hälften) wird genauso verfahren: Das mittlere Element liefert wieder die Entscheidung darüber, ob und wo weitergesucht werden muss. Die Länge des Suchbereiches wird so von Schritt zu Schritt halbiert. Spätestens wenn der Suchbereich auf ein einzelnes Element geschrumpft ist, ist die Suche beendet. Dieses eine Element ist entweder das gesuchte Element, oder das gesuchte Element kommt nicht vor.